#include <iostream>
#include "BinaryTree.h"
using namespace std;

namespace YX 
{
    // 带头结点的单链表实现队列
    
    template<typename T>
    struct forward_list_node
    {
        typedef forward_list_node<T> node;
        node* _next;
        T _data;

        forward_list_node(const T& data)
            :_next(nullptr)
            ,_data(data)
        {

        }

    };

    template<class T>
    class forward_list_queue
    {
        typedef forward_list_node<T> node;
        private:
            node* _head;
            node* _tail;
        public:
            forward_list_queue()
                :_head(nullptr)
                ,_tail(nullptr)
            {
                _head=_tail=new node(T());
            }

            void push(const T& data)
            {
                _tail->_next=new node(data);

                _tail=_tail->_next;
            }

            void pop()
            {
                if(_head->_next==nullptr)
                {
                    return;
                }

                node* del=_head->_next;

                _head->_next=del->_next;

                if(_tail==del)
                {
                    _tail=_head;
                }

                delete del;

            }

            T front()
            {
                if(_head->_next==nullptr)
                {
                    return T();
                }

                return _head->_next->_data;
            }

            T back()
            {
                if(_head==_tail)
                {
                    return T();
                }

                return _tail->_data;
            }
            
            bool empty()
            {
                return _head==_tail;
            }

            size_t size()
            {
                node* curr=_head->_next;

                size_t n=0;

                while(curr!=nullptr)
                {
                    curr=curr->_next;
                    n++;
                }

                return n;
            }

            forward_list_queue(const forward_list_queue<T>& q)
            {
                _head=nullptr;
                _tail=nullptr;
                _head=_tail=new node(T());

                node* curr=q._head->_next;
                while(curr!=nullptr)
                {
                    _tail->_next=new node(curr->_data);
                    _tail=_tail->_next;

                    curr=curr->_next;
                }
            }

            forward_list_queue<T>& operator=(forward_list_queue<T> q)
            {
                std::swap(_head,q._head);
                std::swap(_tail,q._tail);

                return *this;
            }

            ~forward_list_queue()
            {
                while(!empty())
                {
                    pop();
                }

                delete _head;

                _head=_tail=nullptr;
            }
    };

//    namespace YX 
//    {
//        template<typename W>
//        struct BinaryTreeNode
//        {
//            BinaryTreeNode<W>* _left;
//            BinaryTreeNode<W>* _right;
//            W _w;
//
//            BinaryTreeNode(const W& w)
//                :_left(nullptr)
//                ,_right(nullptr)
//                ,_w(w)
//            {
//
//            }
//        };
//
//
//    };

};


int main()
{
    



    YX::TestBinaryTree();


   // YX::forward_list_queue<int> q;

   // q.push(1);
   // q.push(2);
   // q.push(3);
   // q.push(4);
   // q.push(5);

   // YX::forward_list_queue<int> copy(q);

   // q=copy;

   // while(!q.empty())
   // {
   //     cout<<q.front()<<" ";
   //     q.pop();
   // }
   // cout<<endl;

    return 0;
}

